package com.lw.leetcode.other.b;

/**
 * Created with IntelliJ IDEA.
 * 990. 等式方程的可满足性
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/7 13:12
 */
public class EquationsPossible {

    public boolean equationsPossible(String[] equations) {

        Node[] arr = new Node[26];
        int count = 1;

        for (String equation : equations) {
            if (equation.charAt(1) == '=') {
                int i = equation.charAt(0) - 'a';
                int j = equation.charAt(3) - 'a';
                if (arr[i] == null && arr[j] == null) {
                    Node item = new Node(count++);
                    arr[i] = item;
                    arr[j] = item;
                } else if (arr[i] == null) {
                    arr[i] = arr[j];
                } else if (arr[j] == null) {
                    arr[j] = arr[i];
                } else {
                    arr[j].value = arr[i].value;
                }
            }
        }

        for (String equation : equations) {
            if (equation.charAt(1) == '!') {
                int i = equation.charAt(0) - 'a';
                int j = equation.charAt(3) - 'a';
                if (i == j || (arr[j] != null && arr[i] != null && arr[j].value == arr[i].value)) {
                    return false;
                }
            }
        }
        return true;
    }

    class Node {
        private int value;
        public Node(int value) {
            this.value = value;
        }
    }

}
